public class Basics
{
    /**
     * a = dividendo. d = divisor. q = cociente. r = residuo
     * q = a div d
     * a/d
     */
    public int getCociente (int a, int d) {
        int q = 0;
        int r = Math.abs(a);
        
        while (r >= d) {
            r = r - d;
            q = q + 1;
        }
        if (a < 0 && r > 0) {
            r = d - r;
            q = -(q + 1);
        }
        else {
            if (a < 0) {
                q = -q;
            }
        }
        return q;
    }
    /**
     * a = dividendo. d = divisor. q = cociente. r = residuo
     * r = a mod d
     * a%d
     */
    public int getResiduo (int a, int d) {
        int q = 0;
        int r = Math.abs(a);
        
        while (r >= d) {
            r = r - d;
            q = q + 1;
        }
        if (a < 0 && r > 0) {
            r = d - r;
            q = -(q + 1);
        }
        else {
            if (a < 0) {
                q = -q;
            }
        }
        return r;
    }
    /**
     * x = b^n mod m
     */
    public int exponenciacionModular (int b, int n, int m) {
        int x = 1;
        int potencia = b%m;
        String nStr = Integer.toBinaryString(n);
        
        for (int i = nStr.length() - 1; i >= 0; --i) {
            String posStr = nStr.charAt(i) + "";
            int pos = Integer.parseInt(posStr);
            if (pos == 1) {
                x = (x*potencia)%m;
            }
            potencia = (potencia*potencia)%m;
        }
        
        return x;
    }
    /**
     * x = mcd (a,b)
     */
    public int mcdEuclides (int a, int b) {
        int x = Math.max(a,b);
        int y = Math.min(a,b);
        
        while (y > 0) {
            int r = x%y;
            x = y;
            y = r;
        }
        return x;
    }
    /**
     * mcd (a,b) como c.l de a y b
     * mcd (a,b) = s*a + t*b
     */
    public String mcdEuclidesExt (int a, int b) {
        int x = Math.max(a,b);
        int y = Math.min(a,b);
        int sAA = 1; //s anterior anterior
        int sA = 0; //s anterior
        int tAA = 0;
        int tA = 1;
        
        while (y > 0) {
           int q = x/y;
           int r = x%y;
           x = y;
           y = r;
           int s = sAA - q*sA;
           int t = tAA - q*tA;
           sAA = sA;
           tAA = tA;
           sA = s;
           tA = t;
        }
        return x + " = " + sAA + "*" + Math.max(a,b) + " + " + tAA + "*" + Math.min(a,b);
    }
    /**
     * Euclides ext con el return cambiado
     */
    public int invModular (int a, int m) {
        int x = Math.max(a,m);
        int y = Math.min(a,m);
        int sAA = 1; //s anterior anterior
        int sA = 0; //s anterior
        int tAA = 0;
        int tA = 1;
        
        while (y > 0) {
           int q = x/y;
           int r = x%y;
           x = y;
           y = r;
           int s = sAA - q*sA;
           int t = tAA - q*tA;
           sAA = sA;
           tAA = tA;
           sA = s;
           tA = t;
        }
        return (Math.max(a,m) == a) ? a : m;
    }
}
